Algorithmes de recherche
Contents
Algorithmes de recherche#
En informatique, un tableau est une structure de données représentant une séquence finie d’éléments auxquels on peut accéder par leur position dans la séquence. On utilisera des listes Python pour représenter ces tableaux. On peut également remarquer qu’une chaîne de caractères est un tableau de caractères.
On s’intéresse dans ce paragraphe à divers algorithmes permettant de traiter des tableaux ou de retrouver de l’information dans ceux-ci.
Recherche d’un élément#
On cherche à savoir si une valeur donnée fait bien partie des éléments d’un tableau. On parcourt tout simplement ce tableau et on renvoie True dès qu’on trouve cette valeur dans le tableau. Si la valeur n’a pas été trouvée à la fin du parcours, on renvoie False.
def appartient(valeur, tableau):
for element in tableau:
if element == valeur:
return True
return False
appartient('Alice', ['Alice', 'Bob', 'Charles-Antoine'])
True
appartient('Dédé', ['Alice', 'Bob', 'Charles-Antoine'])
False
Note
Le langage Python dispose de l’opérateur in pour déterminer si une valeur appartient à une liste.
'Alice' in ['Alice', 'Bob', 'Charles-Antoine']
True
'Dédé' in ['Alice', 'Bob', 'Charles-Antoine']
False
On peut modifier l’algorithme precédent afin qu’il renvoie l’indice du tableau où on a trouvé la valeur recherché et None si la valeur n’a pas été trouvée.
def indice(valeur, tableau):
for i in range(len(tableau)):
if tableau[i] == valeur:
return i
return None
indice(2, [5, 4, 1, 2, 3])
3
print(indice(6, [5, 4, 1, 2, 3]))
None
Note
La méthode index de la classe list permet de déterminer l’indice d’une valeur dans une liste.
[5, 4, 1, 2, 3].index(2)
3
[5, 4, 1, 2, 3].index(6)
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
Input In [10], in <cell line: 1>()
----> 1 [5, 4, 1, 2, 3].index(6)
ValueError: 6 is not in list
Recherche du maximum#
def maximum(tableau):
m = None
for element in tableau:
if m == None or m < element:
m = element
return m
maximum([4, 5, 8, 1, 3])
8
print(maximum([]))
None
def argmax(tableau):
index = None
for i in range(len(tableau)):
if index == None or tableau[index] < tableau[i]:
index = i
return index
argmax([4, 5, 8, 1, 3])
2
print(argmax([]))
None
def second_maximum(tableau):
m1 = None
m2 = None
for element in tableau:
if m1 == None or m1 < element:
m2 = m1
m1 = element
elif m2 == None or m2 < element:
m2 = element
return m2
second_maximum([4, 5, 8, 1, 3])
5
print(second_maximum([]))
None
print(second_maximum([2]))
None
Comptage des éléments d’un tableau#
def comptage(tableau):
d = {}
for element in tableau:
if element in d:
d[element] += 1
else:
d[element] = 1
return d
comptage(['Alice', 'Bob', 'Alice', 'Charles', 'Charles', 'Alice'])
{'Alice': 3, 'Bob': 1, 'Charles': 2}
Recherche d’un motif dans une chaîne#
def recherche_motif(motif, chaine):
n = len(chaine)
m = len(motif)
for ind in range(n-m+1):
nb = 0
while nb < m and chaine[ind+nb] == motif[nb]:
nb +=1
if nb == m:
return True
return False
recherche_motif("pipa", "pitapipapa")
True
recherche_motif("tapa", "patapipapa")
False
Recherche des deux valeurs les plus proches d’un tableau#
def plus_proches_valeurs(tableau):
valeurs = None
for i in range(len(tableau)):
for j in range(i+1, len(tableau)):
if valeurs == None or abs(tableau[i] - tableau[j]) < abs(valeurs[0] - valeurs[1]):
valeurs = tableau[i], tableau[j]
return valeurs
plus_proches_valeurs([7, 4, 9, 13])
(7, 9)
print(plus_proches_valeurs([]))
None
print(plus_proches_valeurs([7]))
None
Tri à bulles#
Le tri à bulles fait partie des algorithmes de tri classiques. Trier un tableau consiste à ordonner ses éléments du plus petit au plus grand. On suppose donc que les éléments du tableau sont à valeurs dans un ensemble muni d’une relation d’ordre total.
Le tri à bulles consiste à déplacer les éléments du plus grand au plus petit vers la fin du tableau comme des bulles d’air dans un liquide. Plus précisément :
on parcourt le tableau en comparant les couples d’éléments consécutifs ;
si deux éléments consécutifs ne sont pas dans le bon ordre, on les échange ;
à la fin de ce premiers parcours du tableau, on peut garantir que le plus grand élément du tableau est en dernière position ;
on répète alors ce qui précède sur le tableau privé de son dernier élément et ainsi de suite jusqu’à tri complet du tableau.
def tri_bulles(tableau):
for i in reversed(range(len(tableau))):
for j in range(i):
if tableau[j+1] < tableau[j]:
tableau[j], tableau[j+1] = tableau[j+1], tableau[j]
t = [4, 2, 5, 3, 8, 7, 6, 1]
tri_bulles(t)
t
[1, 2, 3, 4, 5, 6, 7, 8]
t = []
tri_bulles(t)
t
[]
t = [4]
tri_bulles(t)
t
[4]